package utils

import (
	"sort"
)

type SortedList struct {
	inner *[]interface{}
	less  func(e0, e1 interface{}) bool
}

func NewSortedList(inner *[]interface{}, lessfun func(e0, e1 interface{}) bool) *SortedList {
	rval := &SortedList{inner: inner, less: lessfun}
	return rval
}

func (this *SortedList) Append(e interface{}) {
	*this.inner = AppendSortedList(*this.inner, e, func(i int) bool {
		return !this.less((*this.inner)[i], e)
	})
}

func (this *SortedList) DeleteOne(comp func(e interface{}) bool) {
	*this.inner = DeleteSortedList(*this.inner, func(i int) bool {
		return comp((*this.inner)[i])
	})
}

func (this *SortedList) DeleteIdx(idx int) {
	lst := *this.inner
	*this.inner = append(lst[:idx], lst[idx+1:]...)
}

/*
**

	lst 根据lessfun 进行过排序
*/
func SortedListBinaryFind(lst []interface{}, lessfun func(i int) bool, compfun func(i int) bool) int {
	var index = -1
	var idx0 = 0
	var leftIndex = 0
	var rightIndex = len(lst) - 1
	for {
		if leftIndex > rightIndex {
			break
		}
		idx0 = (leftIndex + rightIndex) / 2
		if compfun(idx0) {
			index = idx0
			break
		} else if !lessfun(idx0) {
			rightIndex = idx0 - 1
		} else {
			leftIndex = idx0 + 1
		}
	}
	return index
}

/*
*
 */
func AppendSortedList(lst []interface{}, e interface{}, compfun func(i int) bool) []interface{} {
	n := len(lst)
	i := sort.Search(n, compfun)
	if i == n {
		return append(lst, e)
	}
	// we now know that i points at where we want to insert
	lst = append(lst, e)     // try to grow the slice in place, any entry works.
	copy(lst[i+1:], lst[i:]) // Move shorter entries down
	lst[i] = e
	return lst
}

func DeleteSortedList(lst []interface{}, compfun func(i int) bool) []interface{} {
	n := len(lst)
	idx := -1

	/**
	  只能循环
	*/
	for i := 0; i < n; i++ {
		if compfun(i) {
			idx = i
			break
		}
	}

	if idx >= 0 {
		return append(lst[:idx], lst[idx+1:]...)
	} else {
		return lst
	}

}

/*
*

	  查找相等的idx, 插入idx
	  cmpfun
		0:  = equal
	    -1: less
	     1: greater
*/
func QuickSearchOrInsertIdx(n int, cmpfun func(int) int) (findIdx, insertIdx int) {
	findIdx = -1
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		r := cmpfun(h)
		if r == 0 { // equal
			findIdx = h
			i = h + 1
			break
		} else if r > 0 {
			i = h + 1
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	insertIdx = i
	return
}

/*
*

	0: v0 == v1

-1: v0 < v1

	1: v1 > v1
*/
func CompareIntValFunc(v0, v1 int) int {
	if v0 == v1 {
		return 0
	} else if v0 < v1 {
		return -1
	}
	return 1

}
